An embedded device like an IC card uses a portion of a solid-state semiconductor memory to store non-volatile data. The category of non-volatile data includes application executables, files, passwords, cryptographic keys, certificates, user profiles, as well as operating system status variables, application status variables, the application registry, and so on. The content of all the above data is variable during the operating phase of the device, but their values are preserved during power off.
On the contrary, the volatile data is lost during a power off phase and is initialized at the device start-up. The category of volatile data includes the CPU stack, buffers for I/O operations, buffers for temporary computations, and so on.
The non-volatile memory assures that the non-volatile data is not lost following a regular switch-off of the device, i.e., when the electrical deactivation occurs in an idle state of the device. This is the typical case when the deactivation is driven by the logic of the terminal that the device is connected to.
If an accidental electrical deactivation occurs during an application execution, specifically during an updating operation of complex non-volatile data, it is possible that the value of data is left in an inconsistent state. This could completely or partially compromise the functioning or the security of the device in the successive power-on sessions.
To address this problem, operating systems provide a known mechanism of transaction. The transaction mechanism provides to the application layer the instruments to group together an arbitrary number of writing operations, establishing that they have to be considered as a single writing operation with respect to events like a power off. The application has to mark all the writing operations between two instructions. In other words, all the write operations are to be included between two instructions, namely Begin Transaction and Commit Transaction, as schematically shown in FIG. 1.
In case of power off during the execution of the code included between the two instructions Begin Transaction and Commit Transaction, the operating system assures that the values of all the non-volatile data affected by the Secure Updates are restored, at the next device start-up, to the value they had before the statement Begin Transaction. Advanced implementations allow multilevel transactions, with nested levels of Begin Transaction and Commit Transaction instructions.
The transaction mechanism can be implemented by using a transaction stack, as will be clear by the following description and as supported by FIGS. 2a-2e. In these figures, the possible states of execution of a transaction, comprising two Secure Operations, are indicated with reference number 10. In particular, in FIG. 2a the transaction is in an Initial state, in FIG. 2b the transaction is in a Begin Transaction state, in FIG. 2c the transaction is in a Secure Update state, in FIG. 2d the transaction is still in the Secure Update state and, finally, in FIG. 2e the transaction is in a Commit Transaction state.
In FIGS. 2a-2e, the non-volatile memory is also schematically shown and indicated with reference number 20. Values during all the possible states of transaction execution are indicated inside the cells of the non-volatile memory 20. In particular, the start address of the non-volatile memory 20 in which data will be written by the first secure operation is indicated with A1, and the length of data to be written during the first secure operation is indicated with L1.
Similarly, the start address of the non-volatile memory 20 in which data will be written by the second secure operation is indicated with A2, and the length of data to be written during the second secure operation is indicated with L2. The transaction stack is indicated with 30, and the top pointer to the transaction stack is indicated with 40.
The transaction stack 30 is cleaned at the start of Begin Transaction when the transaction is in the Initial state. Each Secure Updating operation, as shown in FIGS. 2c and 2d, adds a record on the transaction stack 30. This contains the information to recover the original value of that data after a potential unexpected power off (typically the data address/size/value). At the start of Commit Transaction the transaction stack 30 is cleaned again.
FIGS. 3a-3b show the recovery, at the device start-up, of the original data values in case of device power off during the first Secure Update operation. In particular, FIG. 3a schematically shows the device start-up after an incorrect power off that caused some data in the non-volatile memory 20 to be lost, with the lost data being indicated with the symbols “???.” In FIG. 3b a Rollback transaction restores the lost data inside their original position by recovering the right values from the transaction stack 30.
FIG. 5 instead gives an example of the transaction stack 30 usage for the case of eight consecutive transactions containing a different number of Secure Updating operations. The transactions indicated with numbers 1, 3, 5, 6, 7 and 8 contain just one update, the transaction number 2 contains 2 updates and the transaction number 4 contains 3 updates. FIG. 6 displays a graph showing the total number of writing operations following the eight transactions schematically shown in FIG. 5.
If the device deactivation is regular, there is no application execution ongoing. Then at the device start-up the transaction stack 30 is always empty. If the device is deactivated while an application is working and the execution flow is between the two instructions Begin Transaction and Commit Transaction, then the operating system, at the next start-up, finds the transaction stack 30 not empty and carries out all the recovery operations according the records on the transaction stack 30. After that, the stack is clean.
Implementation of the transaction stack 30 needs a non-volatile variable to store the pointer to the top of the transaction stack 30 (Top in the following). The value of Top is itself sensitive data with respect to an accidental power-off event. So, a dedicated mechanism, independent from the transaction stack, is required to assure the atomicity of the Top variable. This is typically obtained by a dedicated pointerless circular buffer. This approach is feasible because the Top variable is a single, short and predefined-size data (2 or 4 bytes). FIG. 4 shows an example of an atomic updating mechanism for the Top pointer by way of a 5-slot pointerless circular buffer. Each slot is tagged with a binary flag (0 or 1). In each time slot, the current value of Top is contained in the first slot tagged with 0, from left to right.
The non-volatile memory 20 allows a limited number of writing accesses. Over this limit, the data retention time of the non-volatile memory 20 decreases to values not acceptable for any applicable purpose. For example, the number of the allowed writing operations for EEPROM or Flash memories is typically in the range of 100,000 to 1,000,000, independently for each memory cell.
This limitation has a large impact on the standard implementation of the transaction mechanism, as any secure writing operation performed by the applications has the side effect of a further writing operation in the transaction stack 30. More particularly, the first secure writing operation of any transaction (the instructions Secure Update 1 in FIG. 5) causes a writing access to the first byte of the transaction stack 30. The maximum number of writing accesses to this byte bounds the number of the secure updating operations allowed to the applications, irrespective of where the applications write. Even if the device is guaranteed for 100,000 writing operations on each single byte of the non-volatile memory 20, the applications cannot perform more than 100,000 secure updatings, even on different non-volatile memory areas. This is because in opposite cases, the first bytes of the transaction stack 30 could be damaged.
An approach to this limitation could be an implementation of the transactions stack 30 in a circular buffer, where all the bytes are stressed in the same way. Nevertheless, a circular implementation is much more difficult compared to a linear one because of the nature of the transaction mechanism. Each transaction includes one or more records, with different lengths, and nested in case of nested transactions. Moreover, the reuse of the implementation of a linear stack for a circular stack is rather hard.